/*
 *    AgrawalSrikantItemsetGenerator.java
 *    Copyright (C) 2010 University of Waikato, Hamilton, New Zealand
 *    @author Celia Biguzzi, Albert Bifet
 *
 *    This program is free software; you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation; either version 2 of the License, or
 *    (at your option) any later version.
 *
 *    This program is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with this program; if not, write to the Free Software
 *    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

package moa.streams.generators;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

import weka.core.Attribute;
import weka.core.FastVector;
import weka.core.Instance;
import weka.core.Instances;
import moa.core.InputStreamProgressMonitor;
import moa.core.InstancesHeader;
import moa.core.ObjectRepository;
import moa.core.MiscUtils;
import moa.options.AbstractOptionHandler;
import moa.options.FloatOption;
import moa.options.IntOption;
import moa.streams.InstanceStream;
import moa.tasks.TaskMonitor;

// Itemset Generator described in the paper:
//   Rakesh Agrawal, Ramakrishnan Srikant
//    "Fast Algorithms for Mining Association Rules in Large Databases", 
//     VLDB '94: Proceedings of the 20th International Conference on Very Large Data Bases,
//      pages 487-499, 1994.
// Public C++ source code available at:
//   http://www.almaden.ibm.com/software/quest/Resources/datasets/syndata.html#assocSynDat
//


public class AgrawalSrikantItemsetGenerator extends AbstractOptionHandler implements InstanceStream {

	@Override
	public String getPurposeString() {
		return "Generates itemsets simulating transactions in a retailing environment.";
	}

	public FloatOption averageSizeTransactionOption = new FloatOption(
			"averageSizeTransaction", 's',
			"Average size of the transactions.", 10);
			
	public FloatOption averageSizeMaximalPotentiallyFrequentItemsetsOption = new FloatOption(
			"averageSizeMaximalPotentiallyFrequentItemsets", 'm',
			"Average size of the maximal potentially frequent itemsets.", 4);
	
	public IntOption numberOfMaximalPotentiallyFrequentItemsetsOption = new IntOption(
			"numberOfMaximalPotentiallyFrequentItemsets", 'p',
			"Number of maximal potentially frequent itemsets", 2000);		

	public IntOption numberItemsOption = new IntOption(
			"numberItems", 'n',
			"Number of items.", 1000);
			
	public FloatOption correlationLevelOption = new FloatOption(
			"correlationLevel", 'c',
			"Correlation Level.", .5);
			
	public IntOption instanceRandomSeedOption = new IntOption(
			"instanceRandomSeed", 'i',
			"Seed for random generation of instances.", 1);		
	
	protected InstancesHeader streamHeader;
	
	protected int numberItems;
	
	protected class Itemset{
		private List<Integer> itemSet;
		public Itemset(int item){
			add(item);
		}
		
		public Itemset(){
			itemSet = new ArrayList<Integer>(); 
		}

		public void add(int value){
			// Add no duplicates, in a sorted way
			int pos = Collections.binarySearch(this.itemSet, value);
    		if (pos < 0)
				this.itemSet.add(-pos-1, value);
		}
		
		public void addAll(Itemset is){
			this.itemSet.addAll(is.getItemset());
			Collections.sort(this.itemSet);
		}
		
		public List<Integer> getItemset(){
			return itemSet;
		}
		
		public int get(int index){
			return itemSet.get(index);
		}
		
		public void remove(int value){
			this.itemSet.remove(value);
		}
		
		public Itemset getRandomItems(int number, Random random){
			Itemset is = new Itemset();
			is.itemSet = new ArrayList<Integer>(this.itemSet);//this.itemSet.clone();

			//Delete items
			while ( is.size()> number) {
				is.remove(random.nextInt(is.size()));
			}
			return is;
		}
		
		public String toString(){
			StringBuffer r = new StringBuffer ();
			for(int attribute : itemSet){
				r.append(attribute);
				r.append(' ');
			}
			return r.toString();
		}

		public int size(){
			return this.itemSet.size();
		}
		
	}
	
   double exponentialDistribution(double lambda, Random random){
		// Returns an exponentially distributed, positive, random deviate of lambda mean.
		//  TO DO: move to moa.core.MiscUtils
		return -Math.log(random.nextDouble())/lambda;
	}
	
   double normalDistribution(double mean, double variance, Random random){
		// Returns a normal distributed, positive, random deviate of mean "mean" and variance "variance".
		//  TO DO: move to moa.core.MiscUtils
		return random.nextGaussian()* Math.sqrt(variance) + mean;
	}
	
   double uniformDistribution(Random random){
		// Returns an uniform distributed, positive, random deviate from 0 to 1
		//  TO DO: move to moa.core.MiscUtils
		return random.nextDouble();
	}
	

	protected Random streamRandom; 
	
	protected tableItemsets tableMaximalPotentiallyFrequentItemsets;
	
    protected class tableItemsets {

		private Itemset[] itemsets;
	
		private double[] weight;
	
		private double[] sumWeight;
	
		private double[] corruptLevel;
	
		private int size;

		public Itemset getItemset(int index){
			return this.itemsets[index];
		}

		public int getSize(){
			return this.size;
		}

		public double getWeight(int index){
			return this.weight[index];
		}

		public double getSumWeight(int index){
			return this.sumWeight[index];
		}

		public double getCorruptLevel(int index){
			return this.corruptLevel[index];
		}

		public tableItemsets(int sizeTable, double averageSizeItemset, double correlationLevel, int numberItems, Random streamRandom){
			this.size = sizeTable;
			this.itemsets = new Itemset[size];
				
			// An itemset is generated by first picking the size of the
			// itemset from a Poisson distribution
			int sizeItemset = 1 + MiscUtils.poisson(averageSizeItemset - 1, streamRandom);


			// Items in the first itemset are chosen randomly		
			this.itemsets[0] = new Itemset();
			while (this.itemsets[0].size() < sizeItemset){
				this.itemsets[0].add(streamRandom.nextInt(numberItems));
			}

			for (int i = 1; i < this.size; i++){
				sizeItemset = 1 + MiscUtils.poisson(averageSizeItemset - 1, streamRandom);
				// Some fraction of items in subsequent itemsets are chosen from the previous itemset
				// An exponential distributed random variable with mean equal to the correlation level
				// is used to decide the fraction for each itemset
			
				int fraction = (int) ( (double) sizeItemset * exponentialDistribution(correlationLevel, streamRandom));
			
				if (fraction > sizeItemset) {
					 fraction  = sizeItemset;
				}
		
				this.itemsets[i] = this.itemsets[i-1].getRandomItems(fraction, streamRandom);		
			
				// The remaining items are picked at random
				while (this.itemsets[i].size() < sizeItemset){
					this.itemsets[i].add(streamRandom.nextInt(numberItems));
				}
			
			}
		
			//Each itemset has a weight associated with it, which corresponds to the probability
			//that this itemset will be picked. 
			this.weight = new double[this.size];
			this.sumWeight = new double[this.size];
		
			//This weight is picked from an exponential distribution with unit mean
			double sum = 0;
			for (int i = 0; i < this.size; i++){
				this.weight[i] = exponentialDistribution(1.0, streamRandom);
				sum += this.weight[i];
			}
			// It is then normalized. We compute a cumulative sum for speed purposes generating new instances.
			double cumulativeSum = 0;
			for (int i = 0; i < this.size; i++){
				this.weight[i] /= sum;
				cumulativeSum += this.weight[i];
				this.sumWeight[i] = cumulativeSum;
			}
		
			//Each itemset has a corruption level c. It is fixed and is obtained from a normal distribution with mean 0.5 and variance 0.1
			this.corruptLevel = new double[this.size];
			for (int i = 0; i < this.size; i++){
				this.corruptLevel[i] = normalDistribution(0.5, 0.1, streamRandom);
			}

		}

		public void print() {
			for (int i = 0; i < this.getSize(); i++)
			System.out.println(i+"/ "+this.getItemset(i).toString());
		}

	}

	

	@Override
	protected void prepareForUseImpl(TaskMonitor monitor, ObjectRepository repository) {
		monitor.setCurrentActivity("Preparing random itemset values...", -1.0);
		restart();	

		//Create a series of potentially frequent itemsets
		this.tableMaximalPotentiallyFrequentItemsets = new tableItemsets(
			(int) this.numberOfMaximalPotentiallyFrequentItemsetsOption.getValue(), 
			(double) this.averageSizeMaximalPotentiallyFrequentItemsetsOption.getValue(), 
			(double) this.correlationLevelOption.getValue(),
			(int) this.numberItemsOption.getValue(),
			this.streamRandom);
				
		generateHeader();
		//Print Table
		//this.tableMaximalPotentiallyFrequentItemsets.print();
		
	}

	private void generateHeader() {
		// TODO Auto-generated method stub
		FastVector attributes = new FastVector();
		Attribute atr = new Attribute("String", (FastVector) null);
		attributes.addElement(atr);
		this.streamHeader = new InstancesHeader(new Instances(
				getCLICreationString(InstanceStream.class), attributes, 0));
		this.streamHeader.setClassIndex(this.streamHeader.numAttributes() - 1);
	}

	public long estimatedRemainingInstances() {
		return -1;
	}

	public InstancesHeader getHeader() {
		return this.streamHeader;
	}

	public boolean hasMoreInstances() {
		return true;
	}

	public boolean isRestartable() {
		return true;
	}

    private boolean usePreviousChoosedItemset = false;
    private int PreviousChoosedItemset = 0; 
    private int chooseItemset(tableItemsets table){
		// Choose an itemset from the series of potentially frequent itemsets 
		if (this.usePreviousChoosedItemset == true) {
			// Use the large itemset that did not fit in the last transaction
			this.usePreviousChoosedItemset = false;
			return this.PreviousChoosedItemset;
		}
		// Itemset chosen by tossing a weighted coin,
	        // where the weight for a side is the probability of picking the associated itemset.
		int i = 0;
		while (i==0){
			double randomValue = uniformDistribution(this.streamRandom);
			for (i = 0; i < table.getSize(); i++){
				if (table.getSumWeight(i) > randomValue) 
				  break;
			}
		}
		this.usePreviousChoosedItemset = false;
		this.PreviousChoosedItemset = i-1;
		return i-1;
	}

	@Override
	public Instance nextInstance() {
		InstancesHeader header = getHeader();
		Instance inst = new Instance(header.numAttributes());

		//Generate a new itemset
		Itemset itemset = new Itemset();
		int sizeItemset = 1 + MiscUtils.poisson(this.averageSizeTransactionOption.getValue() - 1, this.streamRandom);
		
		while (itemset.size() < sizeItemset){
			//The next itemset to be put in the transaction is chosen by tossing a weighted coin,
			//where the weight for a side is the probability of picking the associated itemset.
			int indexItemsetChoosed = chooseItemset(this.tableMaximalPotentiallyFrequentItemsets);
			
			// If the large itemset on hand does not fit in the transaction, the itemset is put
			// in the transaction anyway in half the cases, and the itemset is moved to
			// the next transaction the rest of the cases.
			Itemset addItemset = this.tableMaximalPotentiallyFrequentItemsets.getItemset(indexItemsetChoosed);
			if (addItemset.size() + itemset.size() > sizeItemset) {
				if (uniformDistribution(this.streamRandom) > 0.5) {
					this.usePreviousChoosedItemset = true;
					break; //continue
				}
			}
							
			// When adding an itemset to a transaction, we keep dropping an item from the itemset as long
			// as uniformly distributed random number between 0 and 1 is less than the corruption level for
			// this itemset.
			double c = this.tableMaximalPotentiallyFrequentItemsets.getCorruptLevel(indexItemsetChoosed);
			
			boolean dropping = true;
			for (int j = 0; j< addItemset.size(); j++) {
				if (dropping == true ) {
					if ( uniformDistribution(this.streamRandom) >= c ){
						// with probability 1-c
						dropping = false;
					}
				} 
				if (dropping == false) {
					itemset.add(addItemset.get(j));
				}
			} 
		}	
		inst.setDataset(header);
		inst.setValue(0, itemset.toString() );

		if (itemset.size() == 0){
			return nextInstance();
		} else {
			//System.out.println(itemset.toString());
			return inst;
		}
	}
	
	public void restart() {
		this.streamRandom = new Random(this.instanceRandomSeedOption
				.getValue());
	}

	@Override
	public void getDescription(StringBuilder sb, int indent) {
		// TODO Auto-generated method stub
		
	}

}
